package com.yanceysong.codetop.s41_s50;

import com.yanceysong.common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;


public class S41_Easy_94_二叉树的中序遍历 {

    /**
     * 二叉树的中序遍历
     * 题目链接: <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/">...</a>
     * ------------------------------------------------------------
     * 题目描述:
     * 给定一个二叉树的根节点 root, 返回其节点值的中序遍历 (Left -> Root -> Right)。
     * ------------------------------------------------------------
     * 示例一:
     * 输入: root = [1,null,2,3]
     * .          1
     * .           \
     * .            2
     * .           /
     * .          3
     * 输出: [1,3,2]
     * 过程: 访问左子树(空) -> 根(1) -> 右子树(2的左子树3, 根2)
     * ------------------------------------------------------------
     * 示例二: root = []  => []
     * 示例三: root = [1] => [1]
     * 示例四: root = [2,1,4,null,null,3] (完全二叉树部分)
     * .           2
     * .         /   \
     * .        1     4
     * .            /
     * .           3
     * .中序: [1,2,3,4]
     * ------------------------------------------------------------
     * 常用 3 种实现方式:
     * 1. 递归 (最直观) - 系统调用栈隐式保存回溯路径。
     * 2. 迭代 + 显式栈 - 手动模拟递归过程, 控制更灵活。
     * 3. Morris 遍历 - 利用线索化思想, O(1) 额外空间, 暂时修改指针再恢复。
     * ------------------------------------------------------------
     * 核心洞察 (Key Insights):
     * - 中序顺序 = 先一路向左入栈 (或递归), 回退时记录根节点, 再转向右子树重复。
     * - Morris 的关键: 对当前节点 curr, 若其左子树存在, 寻找左子树的最右节点 (中序前驱 predecessor)。
     * .  若 predecessor.right 为空, 建立临时线索指向 curr, 然后 curr 左移; 若不为空 (说明左子树已处理), 切断线索并记录 curr, 再右移。
     * - Morris 不使用显式栈, 但会对树做“可逆”修改 (遍历结束后恢复原状)。
     * ------------------------------------------------------------
     * 复杂度分析:
     * 设节点数为 N, 树高 H。
     * - 递归: 时间 O(N), 额外空间 O(H) (递归栈)。
     * - 迭代栈: 时间 O(N), 额外空间 O(H)。
     * - Morris: 时间 O(N), 额外空间 O(1), 但需要指针重连与恢复。
     * ------------------------------------------------------------
     * ASCII Morris 步骤示意 (局部):
     * .      curr=4
     * .      4
     * .     / \
     * .    2   5
     * .   / \
     * .  1   3
     * predecessor = 3 (2 的右链最右); 3.right 指向 4 (建立线索) → 下次回到 4 时能判断左子树已访问。
     * ------------------------------------------------------------
     * 边界测试关注:
     * 1. 空树。
     * 2. 单节点。
     * 3. 只有左链 or 只有右链 (退化链表)。
     * 4. 完全平衡树。
     * 5. 不平衡混合结构。
     * 6. 包含重复值 (不影响遍历顺序, 仅验证顺序稳定性)。
     * ------------------------------------------------------------
     */
    public List<Integer> inorderTraversal(TreeNode rootNode) {
        return inorderTraversalRecursive(rootNode);
    }

    /**
     * 方法一: 递归中序遍历
     * 写法最简洁, 利用系统栈保存回溯路径。
     */
    public List<Integer> inorderTraversalRecursive(TreeNode rootNode) {
        List<Integer> inorderList = new ArrayList<>();
        recursiveHelper(rootNode, inorderList);
        return inorderList;
    }

    private void recursiveHelper(TreeNode current, List<Integer> result) {
        // 终止条件
        if (current == null) {
            return;
        }
        // 1. 左子树
        recursiveHelper(current.left, result);
        // 2. 根节点
        result.add(current.val);
        // 3. 右子树
        recursiveHelper(current.right, result);
    }

    /**
     * 方法二: 迭代 + 栈 (显式模拟递归过程)
     * 思路: 指针沿左侧链下降并压栈, 直到为空; 弹栈访问根, 再转向右子树。
     */
    public List<Integer> inorderTraversalIterative(TreeNode rootNode) {
        List<Integer> inorderList = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cursor = rootNode;
        while (cursor != null || !stack.isEmpty()) {
            // 一路向左: 先把最左路径全部入栈
            while (cursor != null) {
                stack.push(cursor);
                cursor = cursor.left;
            }
            // 此时左侧到底, 弹出栈顶 = 当前要访问的根
            TreeNode node = stack.pop();
            inorderList.add(node.val);
            // 转向其右子树 (右子树再重复上述过程)
            cursor = node.right;
        }
        return inorderList;
    }

    /**
     * 方法三: Morris 中序遍历 (线索二叉树)
     * 额外空间 O(1)。
     * 核心: 为每个有左子树的节点 curr 找到中序前驱 predecessor (其左子树最右节点)。
     * 若 predecessor.right 为空, 建立线索指向 curr, curr 向左; 若已指回 curr, 切断线索并记录 curr, curr 向右。
     */
    public List<Integer> inorderTraversalMorris(TreeNode rootNode) {
        List<Integer> inorderList = new ArrayList<>();
        TreeNode curr = rootNode;
        while (curr != null) {
            if (curr.left == null) {
                // 没有左子树, 直接访问并向右
                inorderList.add(curr.val);
                curr = curr.right;
            } else {
                // 寻找左子树最右节点 (中序前驱)
                TreeNode predecessor = curr.left;
                while (predecessor.right != null && predecessor.right != curr) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    // 第一次到达: 建立线索指向 curr, 转向左子树
                    predecessor.right = curr;
                    curr = curr.left;
                } else {
                    // 第二次到达 (左子树已处理): 断开线索, 访问 curr, 转向右子树
                    predecessor.right = null; // 恢复结构
                    inorderList.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return inorderList;
    }

    /**
     * 主函数: 运行多组测试用例, 验证三种实现一致性与正确性。
     */
    public static void main(String[] args) {
        S41_Easy_94_二叉树的中序遍历 solution = new S41_Easy_94_二叉树的中序遍历();
        System.out.println("=== 二叉树中序遍历测试开始 ===");

        // 测试1: 空树
        System.out.println("\n--- 测试1: 空树 ---");
        testEmpty(solution);

        // 测试2: 单节点
        System.out.println("\n--- 测试2: 单节点 ---");
        testSingleNode(solution);

        // 测试3: 仅左链
        System.out.println("\n--- 测试3: 仅左链 ---");
        testOnlyLeftChain(solution);

        // 测试4: 仅右链
        System.out.println("\n--- 测试4: 仅右链 ---");
        testOnlyRightChain(solution);

        // 测试5: 题目示例 [1,null,2,3]
        System.out.println("\n--- 测试5: 示例树 [1,null,2,3] ---");
        testLeetCodeExample(solution);

        // 测试6: 完全/平衡结构
        System.out.println("\n--- 测试6: 平衡树 ---");
        testBalanced(solution);

        // 测试7: 不平衡混合结构
        System.out.println("\n--- 测试7: 不平衡树 ---");
        testUnbalanced(solution);

        // 测试8: 含重复值
        System.out.println("\n--- 测试8: 含重复值 ---");
        testWithDuplicates(solution);

        // 测试9: 大致形状 + 回归一致性
        System.out.println("\n--- 测试9: 随机构造多棵树一致性 (简化) ---");
        testRandomSmallTrees(solution);

        // 测试10: Morris 恢复结构验证
        System.out.println("\n--- 测试10: Morris 结构恢复 ---");
        testMorrisStructureRestoration(solution);

        System.out.println("\n=== 全部测试完成 (若无断言失败即通过) ===");
    }

    // ===================== 测试用例与辅助函数 =====================

    private static void assertAllEqual(List<Integer> expected, List<Integer> r1, List<Integer> r2, List<Integer> r3) {
        assert expected.equals(r1) : "递归结果不符, expected=" + expected + ", actual=" + r1;
        assert expected.equals(r2) : "迭代结果不符, expected=" + expected + ", actual=" + r2;
        assert expected.equals(r3) : "Morris结果不符, expected=" + expected + ", actual=" + r3;
    }

    private static void printResult(String title, List<Integer> list) {
        System.out.println(title + list);
    }

    private static void testEmpty(S41_Easy_94_二叉树的中序遍历 s) {
        TreeNode root = null;
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(new ArrayList<>(), r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testSingleNode(S41_Easy_94_二叉树的中序遍历 s) {
        TreeNode root = new TreeNode(42);
        List<Integer> expected = List.of(42);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testOnlyLeftChain(S41_Easy_94_二叉树的中序遍历 s) {
        // 形状: 4 -> 3 -> 2 -> 1 (全部在左侧)
        TreeNode root = new TreeNode(4,
                new TreeNode(3,
                        new TreeNode(2,
                                new TreeNode(1), null), null), null);
        List<Integer> expected = List.of(1, 2, 3, 4);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testOnlyRightChain(S41_Easy_94_二叉树的中序遍历 s) {
        // 形状: 1 -> 2 -> 3 -> 4 (全部在右侧)
        TreeNode root = new TreeNode(1, null,
                new TreeNode(2, null,
                        new TreeNode(3, null,
                                new TreeNode(4))));
        List<Integer> expected = List.of(1, 2, 3, 4);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testLeetCodeExample(S41_Easy_94_二叉树的中序遍历 s) {
        // 示例: [1,null,2,3]
        TreeNode root = new TreeNode(1, null,
                new TreeNode(2, new TreeNode(3), null));
        List<Integer> expected = List.of(1, 3, 2);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testBalanced(S41_Easy_94_二叉树的中序遍历 s) {
        // 构造平衡树:         4
        //                 /   \
        //                2     6
        //               / \   / \
        //              1  3  5  7
        TreeNode root = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1), new TreeNode(3)),
                new TreeNode(6,
                        new TreeNode(5), new TreeNode(7)));
        List<Integer> expected = List.of(1, 2, 3, 4, 5, 6, 7);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testUnbalanced(S41_Easy_94_二叉树的中序遍历 s) {
        // 不平衡结构:         5
        //                  / \
        //                 2   8
        //                /   / \
        //               1   6   9
        //                    \
        //                     7
        TreeNode root = new TreeNode(5,
                new TreeNode(2,
                        new TreeNode(1), null),
                new TreeNode(8,
                        new TreeNode(6, null, new TreeNode(7)),
                        new TreeNode(9)));
        List<Integer> expected = List.of(1, 2, 5, 6, 7, 8, 9);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testWithDuplicates(S41_Easy_94_二叉树的中序遍历 s) {
        // 含重复值:      2
        //              / \
        //             1   2
        //                /
        //               2
        TreeNode root = new TreeNode(2,
                new TreeNode(1),
                new TreeNode(2,
                        new TreeNode(2), null));
        List<Integer> expected = List.of(1, 2, 2, 2);
        List<Integer> r1 = s.inorderTraversalRecursive(root);
        List<Integer> r2 = s.inorderTraversalIterative(root);
        List<Integer> r3 = s.inorderTraversalMorris(root);
        assertAllEqual(expected, r1, r2, r3);
        printResult("输出: ", r1);
    }

    private static void testRandomSmallTrees(S41_Easy_94_二叉树的中序遍历 s) {
        java.util.Random rand = new java.util.Random(123);
        for (int t = 0; t < 50; t++) {
            // 随机生成一个最多高度 ~5 的小树 (可能为空)
            TreeNode root = generateRandomTree(rand, 0, 5, 0.7);
            List<Integer> r1 = s.inorderTraversalRecursive(root);
            List<Integer> r2 = s.inorderTraversalIterative(root);
            List<Integer> r3 = s.inorderTraversalMorris(root);
            assert r1.equals(r2) && r1.equals(r3) : "随机树不一致: r1=" + r1 + ", r2=" + r2 + ", r3=" + r3;
        }
        System.out.println("随机 50 棵小树遍历结果一致");
    }

    private static void testMorrisStructureRestoration(S41_Easy_94_二叉树的中序遍历 s) {
        TreeNode root = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1), new TreeNode(3)),
                new TreeNode(5));
        // 先执行 Morris
        List<Integer> morris = s.inorderTraversalMorris(root);
        // 再执行递归, 若结构被破坏则结果可能不同
        List<Integer> recursive = s.inorderTraversalRecursive(root);
        assert morris.equals(recursive) : "Morris 遍历后结构未恢复!";
        System.out.println("Morris 遍历结构恢复验证通过 -> " + morris);
    }

    // 生成随机树 (概率控制), depth 用于控制高度
    private static TreeNode generateRandomTree(java.util.Random rand, int depth, int maxDepth, double continueProb) {
        if (depth >= maxDepth || rand.nextDouble() > continueProb) {
            return null;
        }
        TreeNode node = new TreeNode(rand.nextInt(50));
        node.left = generateRandomTree(rand, depth + 1, maxDepth, continueProb * 0.85);
        node.right = generateRandomTree(rand, depth + 1, maxDepth, continueProb * 0.85);
        return node;
    }
}
